#include <mem.h>
#include "graph.h"
#include "queue.h"

#define INFINITY 1000

// 访问记录
int visit[MAX_SIZE];

// 记录u到v的最短路径
int min[MAX_SIZE];

/* 找u到v的最短路径长度 */
void dfs(AGraph *graph, int u, int v, int depth) {
    if (NULL == graph) {
        return;
    }

    visit[u] = TRUE;

    if (u == v) {
        min[v] = depth < min[v] ? depth : min[v];
    }

    ArcNode *arc = graph->adj_list[u].first;
    while (NULL != arc) {
        if (FALSE == visit[arc->adjv]) {
            dfs(graph, arc->adjv, v, depth + 1);
        }
        arc = arc->next;
    }

    visit[u] = FALSE;
}

/*
 * 求出无向连通图中
 * 距离顶点 V0 的
 * 最短路径长度为 K 的所有节点。
 */
void dfs_traverse(AGraph *graph, int k) {
    if (NULL == graph) {
        return;
    }

    // 记录最短路径的数组初始化
    for (int j = 0; j < MAX_SIZE; ++j) {
        min[j] = INFINITY;
    }

    // 深度遍历求最短长度
    for (int i = 1; i < graph->vex_num; ++i) {
        memset(visit, 0, sizeof(visit));
        dfs(graph, 0, i, 0);
    }

    // 打印找到的结点
    for (int i = 0; i < graph->vex_num; ++i) {
        if (k == min[i]) {
            printf("%c ", graph->adj_list[i]);
        }
    }
}


int main() {
    setbuf(stdout, NULL);
    AGraph *graph = (AGraph *) malloc(sizeof(AGraph));
    graph->vex_num = 5;
    graph->arc_num = 8;

    graph->adj_list[0] = created_vex('A', created_arc(1));
    graph->adj_list[0].first->next = created_arc(2);
    graph->adj_list[0].first->next->next = created_arc(3);

    graph->adj_list[1] = created_vex('B', created_arc(2));
    graph->adj_list[1].first->next = created_arc(3);

    graph->adj_list[2] = created_vex('C', created_arc(3));
    graph->adj_list[2].first->next = created_arc(4);

    graph->adj_list[3] = created_vex('D', NULL);
    graph->adj_list[4] = created_vex('E', NULL);


    dfs_traverse(graph, 1);

    return 0;
}
